package algorithm.recursion.basic;

import java.lang.reflect.Array;

/**
 * 项目名称: god
 * 包 名 称: algorithm.recursion.basic
 * 类 名 称: Fibonacci
 * 类 描 述: TODO
 * 创建时间: 2020/7/7 10:34 下午
 * 创 建 人: Justice
 */
public class Fibonacci {
    // 最基本
    public static int fib0(int n) {
        if (n <= 2) return 1;
        return fib0(n - 1) + fib0(n - 2);
    }

    // 优化1，用数组存放计算结果，避免重复计算
    public static int fib1(int n) {
        if (n <= 2) return 1;
        int[] array = new int[n + 1];
        array[1] = array[2] = 1;
        return fib1(n, array);
    }

    public static int fib1(int n, int[] array) {
        if (array[n] == 0) {
            array[n] = fib1(n - 1, array) + fib1(n - 2, array);
        }
        return array[n];
    }

    // 去递归调用，迭代
    public static int fib2(int n) {
        if (n <= 2) return 1;
        int[] array = new int[n + 1];
        array[1] = array[2] = 1;
        for (int i = 3; i <= n; i++) {
            array[1] = array[i - 1] + array[i - 2];
        }
        return array[n];
    }

    // 使用滚动数组，每次计算只需要用到数组中的两个元素
    public static int fib3(int n) {
        if (n <= 2) return 1;
        int[] array = new int[2];
        array[0] = array[1] = 1;
        for (int i = 3; i <= n; i++) {
            array[i % 2] = array[(i - 1) % 2] + array[(i - 2) % 2];
        }
        return array[n % 2];
    }

    // 位运算
    public static int fib4(int n) {
        if (n <= 2) return 1;
        int[] array = new int[2];
        array[0] = array[1] = 1;
        for (int i = 3; i <= n; i++) {
            array[i & 1] = array[(i - 1) & 1] + array[(i - 2) & 1];
        }
        return array[n & 1];
    }
}
